package com.example.leetcode.c101_c200.c167;
/**
 * 给定一个已按照 非递减顺序排列  的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
 *
 * 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
 *
 * 你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
 *
 *  
 * 示例 1：
 *
 * 输入：numbers = [2,7,11,15], target = 9
 * 输出：[1,2]
 * 解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
 * 示例 2：
 *
 * 输入：numbers = [2,3,4], target = 6
 * 输出：[1,3]
 * 示例 3：
 *
 * 输入：numbers = [-1,0], target = -1
 * 输出：[1,2]
 *  
 *
 * 提示：
 *
 * 2 <= numbers.length <= 3 * 104
 * -1000 <= numbers[i] <= 1000
 * numbers 按 非递减顺序 排列
 * -1000 <= target <= 1000
 * 仅存在一个有效答案
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

import java.util.Arrays;

/**
 * 两数之和 II - 输入有序数组
 * @author zhanpengguo
 * @date 2021-10-11 8:15
 */
public class Solution {

    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        int l = 0;
        while (l < numbers.length - 1) {
            res[0] = l + 1;
            int r = numbers.length - 1;
            int tmp = target - numbers[l];
            while (r > l) {
                if (numbers[r] == tmp) {
                    res[1] = r + 1;
                    return res;
                }
                if (numbers[r] < tmp) {
                    break;
                }
                r--;
            }
            l++;
        }
        return res;
    }

    public int[] twoSum1(int[] numbers, int target) {
        int low = 0, high = numbers.length - 1;
        while (low < high) {
            int sum = numbers[low] + numbers[high];
            if (sum == target) {
                return new int[]{low + 1, high + 1};
            } else if (sum < target) {
                ++low;
            } else {
                --high;
            }
        }
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        int[] numbers = {2,3,4};
        Solution solution = new Solution();
        int[] ints = solution.twoSum1(numbers, 6);
        System.out.println(Arrays.toString(ints));
    }
}
